# coding=utf-8
"""
Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.
"""
def bsearch(nums, beg, end, target):
    mid = (beg + end) / 2
    if nums[mid] == target:
        return mid
    if nums[beg] == target:
        return beg
    if nums[end] == target:
        return end

    if nums[beg] < nums[mid] and nums[mid] < nums[end]:
        if target < nums[mid]:
            return bsearch(nums, beg, mid-1, target)
        else:
            return bsearch(nums, mid+1, end, target)

    elif nums[end] < nums[beg] and nums[beg] < nums[mid]:
        if target < nums[mid] and target > nums[beg]:
            return bsearch(nums, beg, mid-1, target)
        else:
            return bsearch(nums, mid+1, end, target)
    
    elif nums[mid] < nums[end] and nums[end] < nums[beg]:
        if target < nums[end] and target > nums[mid]:
            return bsearch(nums, mid+1, end, target)
        else:
            return bsearch(nums, beg, mid-1, target)
    return -1

class Solution:
    # @param {integer[]} nums
    # @param {integer} target
    # @return {integer}
    def search(self, nums, target):
        return bsearch(nums, 0, len(nums)-1, target)

if __name__ == '__main__':
    print Solution().search([4, 5, 6, 7, 0, 1, 2], 3)
    print Solution().search([1], 0)
